10118. Сумасшедший ученый

Фермер Джон упорядочил n своих коров, каждая из которых относится к одной из двух пород: Holsteins или Guernseys. Он зафиксировал этот порядок в виде строки из  символов, каждый из которых равен либо H, либо G соответственно. Однако, к несчастью, когда коровы прибыли на ферму и Джон снова выстроил их в ряд, получившаяся строка оказалась отличной от исходной.

Обозначим эти две строки через a и b, где a – исходная строка, которую Фермер Джон хотел увидеть, а b – строка, получившаяся после прибытия коров. Фермер Джон обратился за помощью к своему кузену Бену.

После нескольких месяцев работы Бен создал удивительную машину MCBF-3000, которая умеет выбирать любую подстроку и заменять в ней все символы G на H, а все символы H – на G. Теперь Фермер Джон хочет узнать минимальное количество применений этой машины, необходимое для преобразования строки b в строку a. Помогите Фермеру Джону решить эту задачу.

Вход. В первой строке задано целое число n (1 ≤ n ≤ 1000) – количество коров. Далее следуют строки a и b. Каждая из них состоит только из символов H и G.

Выход. Выведите минимальное количество применений машины MCBF-3000, необходимое для преобразования строки b в строку a.

Пример входа	Пример выхода
7 GHHHGHH HHGGGHH	2

РЕШЕНИЕ

жадность

Анализ алгоритма

Будем просматривать строки a и b слева направо. Рассмотрим позиции, в которых символы строк различаются. Пусть i – индекс первой такой позиции, что a_i ≠ b_i. Это означает, что символ в строке b на позиции i необходимо инвертировать. В этот момент мы фиксируем начало интервала применения машины.

Далее продолжаем двигаться вправо, пока символы строк продолжают отличаться, то есть для всех индексов k из интервала i ≤ k ≤ j выполняется условие a_k ≠ b_k. Как только встречается позиция j + 1, для которой a_j+1 = b_j+1, текущий интервал [i; j] завершается. Этот интервал является максимальным по включению: расширить его ни влево, ни вправо нельзя.

Каждому такому интервалу соответствует ровно одно применение машины MCBF-3000, поскольку машина инвертирует все символы на выбранной подстроке, тем самым одновременно исправляя все несовпадения внутри интервала. Таким образом, ответом на задачу является количество таких максимальных интервалов.

Пример

Для заданного примера существует два непересекающихся интервала, на которых необходимо применить машину MCBF-3000.

Реализация алгоритма

Читаем входные данные.

cin >> n >> a >> b;

В переменной cnt храним длину текущего интервала несовпадений. В переменной res накапливаем ответ – количество применений машины.

res = cnt = 0;

Последовательно обрабатываем символы строк.

for (i = 0; i < n; i++)

Если a_i ≠ b_i, увеличиваем cnt на единицу.

if (a[i] != b[i])

cnt++;

В противном случае (если a_i = b_i), текущий интервал несовпадений завершается: сбрасываем cnt в ноль и увеличиваем счётчик интервалов res на единицу.

else

{

if (cnt > 0) res++;

cnt = 0;

}

Если cnt > 0, это означает, что в конце строки остался незавершённый интервал несовпадений, для которого также необходимо совершить одно применение машины.

if (cnt > 0) res++;

Выводим ответ.

cout << res << endl;

Python реализация

Читаем входные данные.

n = int(input())

a = input()

b = input()

В переменной cnt храним длину текущего интервала несовпадений. В переменной res накапливаем ответ – количество применений машины.

res = cnt = 0

Последовательно обрабатываем символы строк.

for i in range(n):

Если a_i ≠ b_i, увеличиваем cnt на единицу.

if a[i] != b[i]: cnt += 1

В противном случае (если a_i = b_i), текущий интервал несовпадений завершается: сбрасываем cnt в ноль и увеличиваем счётчик интервалов res на единицу.

else:

if cnt > 0: res += 1

cnt = 0

Если cnt > 0, это означает, что в конце строки остался незавершённый интервал несовпадений, для которого также необходимо совершить одно применение машины.

if cnt > 0: res += 1

Выводим ответ.

print(res)